再帰関係は、再帰的定義と明示的な関数解の間にある深い数学的な橋渡しを担い、 分割統治法 戦略の本質を捉えています。自己参照的なステップで数列を定義することで、スターリング数やカタラン数といった組合せ構造から、アッカーマン関数の超指数的成長までモデル化できます。
1. 組合せの多様性
再帰の真の力を発揮するのは、それらが取り扱う数列の広範さです。たとえば、 第二種スターリング数 は次のように定義されます：
$$S_{n+1,k} = S_{n,k-1} + nS_{n,k}$$
これは、$n+1$ 個の要素からなる集合を $k$ 個の空でない部分集合に分割する方法の数を表します。同様に、 カタラン数 ($C_n$) は凸多角形の三角形分割を記述しています——非交差対角線を使って凸五角形を三角形に分割する方法です。
2. 構造モデリングと順列の入れ替え（デラングメント）
再帰は、例えば 順列の入れ替え（デラングメント）という、すべての要素が元の位置にない置換の技術的名称です。これは $D_n$ と表されます。
順列の入れ替えの再帰式
順列の入れ替えの関係は次のように与えられます：
$$D_n - nD_{n-1} = (-1)^n$$
あるいは別表現として：$D_n = (n-1)(D_{n-1} + D_{n-2})$。これは、$n$ 人の人がコートチェックで自分の帽子を間違えて受け取る方法の数を数えます。
3. 増加と複雑さの限界
再帰は、極めて効率的なものと計算上「爆発的」なものを両方定義します：
- 分割統治法アプローチ： 二分探索は $a_n = c a_{n/m} + d$ でモデル化され、対数時間の実行時間を得ます。
- アッカーマン関数： 任意の多項式や指数関数よりも速く増加する再帰的深さを定義します： $$AO(x + 3, y, z + 1) = AO(x + 2, y, AO(x + 3, y, z))$$
🎯 教授の技術的要約
非斉次関係を取り扱う際は、$U_n = V_n + g(n)$ の形を思い出してください。ここで $V_n$ は斉次解です。定数係数の線形斉次関係、たとえば $a_n = c_1 a_{n-1} + c_2 a_{n-2}$ については、特性方程式 $t^2 - c_1 t - c_2 = 0$ の根を求めます。